package tests;

public class Keyongyu {
    static class Node {
        int index;
        String data;
        Node next;

        public Node(String data) {
            this.data = data;
        }

        @Override
        public String toString() {
            if (next == null) {
                return "Node{" + data + "}";
            }
            return "Node{" + data + "}->" + next;
        }
    }

    private static boolean hasRing(Node head) {
        if (head == null || head.next == null)
            return false;
        Node slow = head;
        Node fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Node root = buildNode(new int[]{1, 2, 3, 4, 5, 6, 7, 6, 5, 4, 7, 8, 9}, 5);
        //  System.out.println("链表:" + root);
        System.out.println("是否存在环形:" + hasRing(root));
    }

    private static Node buildNode(int[] datas, int ringIndex) {
        Node last = null;
        Node root = null;
        int index = 0;
        Node tmp = null;
        for (int data : datas) {
            Node node = new Node(String.valueOf(data));
            if (last != null) {
                last.next = node;
            } else {
                root = node;
            }
            if (index == ringIndex) {
                tmp = node;
            }
            last = node;
            index++;
        }
        if (last != null && tmp != null) {
            last.next = tmp;
        }
        return root;
    }
}